package main.Q501_600;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

public class Q561_570 {
    public static void main(String[] args) {
        System.out.println("Question561：数组拆分");
        System.out.println("Question562：");
        System.out.println("Question563：");
        System.out.println("Question564：");
        System.out.println("Question565：数组嵌套");
        System.out.println("Question566：重塑矩阵");
        System.out.println("Question567：字符串的排列");
        System.out.println(Question567.checkInclusion("ab","eidboaoo"));
        System.out.println("Question568：");
        System.out.println("Question569：");
        System.out.println("Question570：");
    }
}

class Question561{
    public int arrayPairSum(int[] nums) {
        Arrays.sort(nums);
        int sum=0;
        for (int i= nums.length-2;i>=0;i-=2) sum+=nums[i];
        return sum;
    }
}

class Question565{
    public static int arrayNesting(int[] nums) {
        int max=0;
        for (int i=0;i< nums.length;i++){
            if (nums[i]==-1) continue;
            int size=1,next=nums[i];
            while (next!=i){
                int temp=nums[next];
                nums[next]=-1;
                size++;
                next=temp;
            }
            max=Math.max(max,size);
        }
//        for (int i=0;i< nums.length;i++){
//            Set<Integer> set=new HashSet<>();
//            set.add(nums[i]);
//            int index=nums[i];
//            while (!set.contains(nums[index])){
//                set.add(nums[index]);
//                index=nums[index];
//            }
//            if (set.size()>max) max=set.size();
//        }
        return max;
    }
}

class Question566{
    public static int[][] matrixReshape(int[][] mat, int r, int c) {
        int m = mat.length;
        int n = mat[0].length;
        if (m * n != r * c) return mat;
        int[][] ans = new int[r][c];
        for (int x = 0; x < m * n; ++x) ans[x / c][x % c] = mat[x / n][x % n];
        return ans;
    }
}

class Question567{
    public static boolean checkInclusion(String s1, String s2) {
        Map<Character,Integer> map=new HashMap<>();
        char[] str1=s1.toCharArray(),str2=s2.toCharArray();
        for (char c:str1) map.put(c,map.getOrDefault(c,0)+1);//将s1的所有字符存入
        for (int i=0;i<s2.length();i++){//在s2中以i开头的子串，是否为s1的排列
            Map<Character,Integer> tempMap=new HashMap<>();
            tempMap.putAll(map);
            for (int j=i;j< str2.length&&j<i+str1.length;j++){
                char curChar=str2[j];
                if (!tempMap.containsKey(curChar)) break;//当前字符在map中不存在，则当前子串不符合要求
                else {
                    if (tempMap.get(curChar)>1) tempMap.put(curChar,tempMap.get(curChar)-1);//个数大于1，-1
                    else tempMap.remove(curChar);//个数等于1，删除
                }
            }
            if (tempMap.isEmpty()) return true;//若map为空，则该子串符合要求
        }
        return false;
    }
}